<?php
/**
 * Created by PhpStorm.
 * User: yiranblade
 * Date: 18-6-28
 * Time: 下午4:59
 */

namespace App\Http\Logic;

class GetMapPath
{
    private $edge;
    private $vexC;
    private $vex;
    private $edgeC;


    public function dijkstra(String $start,String $end){
        $mapData=$this->loadMap();
        $start=$this->getPosition($start);
        $end=$this->getPosition($end);
        if($start==-1||$end==-1){
            return false;
        }
        $prev=array();
        $dist=array();
        $vex=$mapData['vex'];
        $edge=$mapData['edge'];
        $vexC=$mapData['vexC'];
        $flag=array();
        for($i=0;$i<$vexC;$i++){
            $flag[$i]=false;
            $prev[$i]=-1;
            $dist[$i]=$edge[$start][$i];

        }
        $flag[$start]=true;
        $dist[$start]=0;
        $k=0;
        for($i=1;$i<$vexC;$i++){
            $min=PHP_INT_MAX;
            for($j=0;$j<$vexC;$j++){
                if($flag[$j]==false&&$dist[$j]<$min){
                    $min=$dist[$j];
                    $k=$j;
                }
            }
            $flag[$k]=true;
            for($j=0;$j<$vexC;$j++){
                $tmp=$edge[$k][$j]==PHP_INT_MAX?PHP_INT_MAX:$min+$edge[$k][$j];
                if($flag[$j]==false&&($tmp<$dist[$j])){
                    $dist[$j]=$tmp;
                    $prev[$j]=$k;

                }
            }

        }
        return $this->findPath($start,$end,$vex,$dist,$prev);

    }
    private function loadMap()
    {
        $file=fopen("/home/yiranblade/PhpstormProjects/en/resources/mapfile.txt","r");

        $vexC=&$this->vexC;
        $edgeC=&$this->edgeC;
        $vex=&$this->vex;
        $edge=&$this->edge;
        $vexC=intval(fgets($file));
        $edgeC=intval(fgets($file));
        $vex=array();
        $edge=array();
        for ($i=0;$i<$vexC;$i++){

            $tmp=fgets($file);
            $l=strlen($tmp);
            $vex[]=substr($tmp,0, $l-1);
        }
        for($i=0;$i<$vexC;$i++){
            for($j=0;$j<$vexC;$j++){
                if($i==$j)
                    $edge[$i][$j]=0;
                else
                    $edge[$i][$j]= PHP_INT_MAX;
            }
        }
        for($i=0;$i<$edgeC;$i++){
            $c1T=fgets($file);
            $c2T=fgets($file);
            $c1C=strlen($c1T);
            $c2C=strlen($c2T);
            $c1=substr($c1T,0, $c1C-1);
            $c2=substr($c2T,0, $c2C-1);
            $weight=intval(fgets($file));
            $p1=$this->getPosition($c1);
            $p2=$this->getPosition($c2);
            if($p1==-1||$p2==-1){
                dd("************".$c1."*********".$c2);
                dd("************".$p1."*********".$p2);
                return null;
            }
            $edge[$p1][$p2]=$weight;
            $edge[$p2][$p1]=$weight;


        }
        fclose($file);
        return [
        'edgeC'       => $edgeC,
         'vexC'=>$vexC,
        'vex'     => $vex,
        'edge' => $edge,
        ];

    }
    private function findPath(int $start,int $end,array $vex,array $dist,array $prev){
        $path="";
        for ($i=$prev[$end];$i!=-1;$i=$prev[$i]){
            $path=$vex[$i].'->'.$path;
        }
        $path=$vex[$start].'->'.$path.$vex[$end];
        return [
            'start'=>$vex[$start],
            'end'=>$vex[$end],
            'distance'=>$dist[$end],
            'path'=>$path

        ];
    }
    private function getPosition(String $ch):int{
        $vex=$this->vex;
        $vexC=$this->vexC;
        for($i=0;$i<$vexC;$i++){
            if($vex[$i]==$ch){
                return $i;
            }
        }
        return -1;
    }

}